LeetCode——组合总数

NO.39 组合总数 中等

思路一：深度遍历，回溯法 深度遍历得到”全排列“的过程中回溯剪枝。目标值作为根节点，每个分做减法，如果目标值被减为0则结算此分支路径上的减数集合，如果目标值被减为负数则剪枝即可。

去重：每个分支节点上的减数的下标不能比本分支上一层节点的减数的下标小。即，上层节点的减数下标为3，则同分支下一层节点的减数下标要从3开始。(这样每个分支就不会重复使用之前使用过的元素)

List<List<Integer>> res=new ArrayList<>();
public List<List<Integer>> combinationSum(int[] candidates, int target) {
    if (candidates==null)return res;
    dfs(target,0,new Stack<Integer>(),candidates);
    return res;
}
//深度遍历
private void dfs(int target, int index, Stack<Integer> pre, int[] candidates) {
    //等于零说明结果符合要求
    if (target==0){
        res.add(new ArrayList<>(pre));
        return;
    }
    //遍历，index为本分支上一节点的减数的下标
    for (int i=index;i<candidates.length;i++){
        //如果减数大于目标值，则差为负数，不符合结果
        if (candidates[i]<=target){
            pre.push(candidates[i]);
            //目标值减去元素值
            dfs(target-candidates[i],i,pre, candidates);
            //每次回溯将最后一次加入的元素删除
            pre.pop();
        }
    }
}

---

本人菜鸟，有错误请告知，感激不尽！

更多题解和学习记录博客:博客、github